package 排序.归并排序;

import java.util.Arrays;
/*
归并排序加一行代码即可求数组中的逆序对个数
在本地ide通过，在云端不通过，在线编程有一些限制
 */
public class test
{
    public int reverseCount =0;
    public void Sort(int[] arr)
    {
        int[] temp=new int[arr.length];
        Sort(arr,0,arr.length-1,temp);
    }
    public void Sort(int[] arr,int left,int right,int[] temp)
    {
        if (left<right)
        {
            int mid=(left+right)/2;
            Sort(arr, left, mid, temp);
            Sort(arr, mid+1, right, temp);
            if (arr[mid]<=arr[mid+1])
                return;
            Merge(arr,left,mid,right,temp);
        }
    }
    public void Merge(int[] arr,int left,int mid ,int right,int[] temp)
    {
        //定义指针
        int i=left;//左序列指针
        int j=mid+1;//右序列指针
        int t=0;//临时数组指针

        //较小的进入temp
        while (i<=mid&&j<=right)
        {
            if (arr[i]<=arr[j])
            {
                temp[t++]=arr[i++];
            }
            else
            {
                temp[t++]=arr[j++];
                this.reverseCount+=mid-i+1;
            }
        }
        //如果有剩余元素，直接进入temp
        while (i<=mid)
        {
            temp[t++]=arr[i++];
        }
        while(j<=right)
        {
            temp[t++]=arr[j++];
        }
        //复制到arr数组中去
        t=0;
        while (left<=right)
        {
            arr[left++]=temp[t++];
        }
    }

    public static void main(String[] args)
    {
        int [] arr = {1,2,3,4,5,6,7,0};
        test t=new test();
        t.Sort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(t.reverseCount);
    }
}
